{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Best Line LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #geometry #array #hash-table #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #几何 #数组 #哈希表 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: bestLine"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最佳直线"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个二维平面及平面上的 N 个点列表<code>Points</code>，其中第<code>i</code>个点的坐标为<code>Points[i]=[X<sub>i</sub>,Y<sub>i</sub>]</code>。请找出一条直线，其通过的点的数目最多。</p>\n",
    "<p>设穿过最多点的直线所穿过的全部点编号从小到大排序的列表为<code>S</code>，你仅需返回<code>[S[0],S[1]]</code>作为答案，若有多条直线穿过了相同数量的点，则选择<code>S[0]</code>值较小的直线返回，<code>S[0]</code>相同则选择<code>S[1]</code>值较小的直线返回。</p>\n",
    "<p><strong>示例：</strong></p>\n",
    "<pre><strong>输入：</strong> [[0,0],[1,1],[1,0],[2,0]]\n",
    "<strong>输出：</strong> [0,2]\n",
    "<strong>解释：</strong> 所求直线穿过的3个点的编号为[0,2,3]\n",
    "</pre>\n",
    "<p><strong>提示：</strong></p>\n",
    "<ul>\n",
    "<li><code>2 <= len(Points) <= 300</code></li>\n",
    "<li><code>len(Points[i]) = 2</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [best-line-lcci](https://leetcode.cn/problems/best-line-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [best-line-lcci](https://leetcode.cn/problems/best-line-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[-38935,27124],[-39837,19604],[-7086,42194],[-11571,-23257],[115,-23257],[20229,5976],[24653,-18488],[11017,21043],[-9353,16550],[-47076,15237],[-36686,42194],[-17704,1104],[31067,7368],[-20882,42194],[-19107,-10597],[-14898,24506],[-20801,42194],[-52268,40727],[-14042,42194],[-23254,42194],[-30837,-53882],[1402,801],[-33961,-984],[-6411,42194],[-12210,22901],[-8213,-19441],[-26939,20810],[30656,-23257],[-27195,21649],[-33780,2717],[23617,27018],[12266,3608]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        n = len(points)\n",
    "        cnt = 0\n",
    "        res = [inf, inf]\n",
    "        for i in range(n):\n",
    "            d = {}\n",
    "            x1, y1 = points[i]\n",
    "            for j in range(i+1, n):\n",
    "                x2, y2 = points[j]\n",
    "                if x2 - x1 == 0:\n",
    "                    k = inf \n",
    "                else:\n",
    "                    k = (y2 - y1) / (x2 - x1) \n",
    "                if k not in d:\n",
    "                    d[k] = []\n",
    "                d[k].append(j)\n",
    "\n",
    "            for k, v in d.items():\n",
    "                if len(v) > cnt:\n",
    "                    cnt = len(v)\n",
    "                    res = [i] + v[:1]             \n",
    "                elif len(v) == cnt:\n",
    "                    res = min(res, [i] + v[:1])\n",
    "\n",
    "        return res \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        ansnum=0\n",
    "        ans=[]\n",
    "        for i in range(len(points)):\n",
    "            x,y=points[i]\n",
    "            dict=defaultdict(list)\n",
    "            for j in range(i+1,len(points)):\n",
    "                tx,ty=points[j]\n",
    "                if tx-x==0:\n",
    "                    dict[\"inf\"].append(j)\n",
    "                else:\n",
    "                    k=(ty-y)/(tx-x)\n",
    "                    dict[k].append(j)\n",
    "            for k in dict:\n",
    "                if len(dict[k])+1>ansnum:\n",
    "                    ans=[i]+dict[k]\n",
    "                    ansnum=len(dict[k])+1\n",
    "        return ans[0:2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        n = len(points)\n",
    "        cur = 0\n",
    "        for i in range(n):\n",
    "            mp = collections.defaultdict(list)\n",
    "            for j in range(i+1, n):\n",
    "                if points[i][0] == points[j][0]:\n",
    "                    mp[inf].append(j)\n",
    "                    continue\n",
    "                k = (points[i][1]-points[j][1])/(points[i][0]-points[j][0])\n",
    "                mp[k].append(j)\n",
    "            \n",
    "            for p in mp.values():\n",
    "                if len(p)+1 > cur:\n",
    "                    cur = len(p)+1\n",
    "                    res = [i, p[0]]\n",
    "                elif len(p)+1 == cur:\n",
    "                    if i < res[0] or (i == res[0] and p[0] < res[1]):\n",
    "                        res = [i, p[0]]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        ansnum=0\n",
    "        ans=[]\n",
    "        for i in range(len(points)):\n",
    "            x,y=points[i]\n",
    "            dict=defaultdict(list)\n",
    "            for j in range(i+1,len(points)):\n",
    "                tx,ty=points[j]\n",
    "                if tx-x==0:\n",
    "                    dict[\"inf\"].append(j)\n",
    "                else:\n",
    "                    k=(ty-y)/(tx-x)\n",
    "                    dict[k].append(j)\n",
    "            for k in dict:\n",
    "                if len(dict[k])+1>ansnum:\n",
    "                    ans=[i]+dict[k]\n",
    "                    ansnum=len(dict[k])+1\n",
    "        return ans[0:2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        from collections import defaultdict \n",
    "        max_len = 0\n",
    "        res = []\n",
    "        for i in range(len(points)):\n",
    "            dic = defaultdict(list)\n",
    "            x, y = points[i]\n",
    "            for j in range(i+1, len(points)):\n",
    "                tx, ty = points[j]\n",
    "                if tx == x:\n",
    "                  dic[float('inf')].append(j)\n",
    "                else:\n",
    "                  slope = (ty-y)/(tx-x)\n",
    "                  dic[slope].append(j)\n",
    "            \n",
    "            for v in dic:\n",
    "                if len(dic[v])+1 > max_len:\n",
    "                    max_len = len(dic[v])+ 1\n",
    "                    res = [i] + dic[v]\n",
    "        return res[0:2]\n",
    "                \n",
    "                \n",
    "        \n",
    "        \n",
    "\n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        max_length = 2\n",
    "        ret = [0, 1]\n",
    "        for i, (x1, y1) in enumerate(points):\n",
    "            counter = dict()\n",
    "            for j in range(len(points)):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                a, b = points[j][0]-x1, points[j][1]-y1\n",
    "                c = gcd(a, b)\n",
    "                k = (a//c, b//c)\n",
    "                if k not in counter:\n",
    "                    counter[k] = list()\n",
    "                if j > i and (not counter[k] or counter[k][-1] < i):\n",
    "                    counter[k].append(i)\n",
    "                counter[k].append(j)\n",
    "\n",
    "            for k in counter:\n",
    "                if len(counter[k]) < max_length:\n",
    "                    continue\n",
    "                elif len(counter[k]) > max_length:\n",
    "                    ret = counter[k][:2]\n",
    "                    max_length = len(counter[k])\n",
    "                else:\n",
    "                    ret = min(ret, counter[k][:2])\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        ansnum=0\n",
    "        ans=[]\n",
    "        for i in range(len(points)):\n",
    "            x,y=points[i]\n",
    "            dict=defaultdict(list)\n",
    "            for j in range(i+1,len(points)):\n",
    "                tx,ty=points[j]\n",
    "                if tx-x==0:\n",
    "                    dict[\"inf\"].append(j)\n",
    "                else:\n",
    "                    k=(ty-y)/(tx-x)\n",
    "                    dict[k].append(j)\n",
    "            for k in dict:\n",
    "                if len(dict[k])+1>ansnum:\n",
    "                    ans=[i]+dict[k]\n",
    "                    ansnum=len(dict[k])+1\n",
    "        return ans[:2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        maxn = 0\n",
    "        for i in range(len(points)):\n",
    "            tmpd = {}\n",
    "            tmpmax = 0\n",
    "            tmpres = []\n",
    "            for j in range(i+1, len(points)):\n",
    "                if points[j][0] - points[i][0] == 0:\n",
    "                    k = '0'\n",
    "                else:\n",
    "                    k = (points[j][1] - points[i][1])/(points[j][0] - points[i][0])\n",
    "\n",
    "                if k in tmpd.keys():\n",
    "                    tmpd[k].append(j)\n",
    "                else:\n",
    "                    tmpd[k] = [i, j]\n",
    "                if len(tmpd[k]) > tmpmax:\n",
    "                    tmpmax = len(tmpd[k])\n",
    "                    tmpres = tmpd[k]\n",
    "                elif len(tmpd[k]) == tmpmax and len(tmpd[k]) > 0:\n",
    "                    # print(tmpd[k], (tmpd[k][0] < tmpres[0] or (tmpd[k][0] == tmpres[0] and tmpd[k][1] < tmpres[1])))\n",
    "                    if tmpd[k][0] < tmpres[0] or (tmpd[k][0] == tmpres[0] and tmpd[k][1] < tmpres[1]):\n",
    "                        tmpmax = len(tmpd[k])\n",
    "                        tmpres = tmpd[k]\n",
    "            if tmpmax > maxn:\n",
    "                res = tmpres\n",
    "                maxn = tmpmax\n",
    "            elif tmpmax == maxn and maxn > 0:\n",
    "                if tmpres[0] < res[0] or (tmpres[0] == res[0] and tmpres[1] < res[1]):\n",
    "                    res = tmpres\n",
    "                    maxn = tmpmax                    \n",
    "        return [res[0], res[1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        # def size(p):\n",
    "        #     return p[0]**2 + p[1]**2\n",
    "\n",
    "        max_pl = []\n",
    "        max_i = []\n",
    "        for i in range(len(points)):\n",
    "            for j in range(i+1, len(points)):\n",
    "                p1 = points[i]\n",
    "                p2 = points[j]\n",
    "                p_l = [p1, p2]\n",
    "                for k in range(j+1, len(points)):\n",
    "                    p3 = points[k]\n",
    "                    if (p2[0]-p1[0])==0 or (p3[0]-p1[0])==0:\n",
    "                        bp12, bp13 = False, False\n",
    "                        try:\n",
    "                            alphap1p2 = (p2[0]-p1[0])/(p2[1]-p1[1])\n",
    "                        except: bp12 = True\n",
    "                        try:\n",
    "                            alphap1p3 = (p3[0]-p1[0])/(p3[1]-p1[1])\n",
    "                        except: bp13 = True\n",
    "                        if bp12 and bp13:\n",
    "                            alphap1p2 = 1\n",
    "                            alphap1p3 = 1\n",
    "                        elif not (bp12==False and bp13==False):\n",
    "                            alphap1p2 = 0\n",
    "                            alphap1p3 = 1\n",
    "                    else: \n",
    "                        alphap1p2 = (p2[1]-p1[1])/(p2[0]-p1[0])\n",
    "                        alphap1p3 = (p3[1]-p1[1])/(p3[0]-p1[0])\n",
    "\n",
    "                    if alphap1p2 == alphap1p3:\n",
    "                        p_l.append(p3)\n",
    "                if len(p_l) > len(max_pl):\n",
    "                    max_pl = p_l\n",
    "                    max_i = [i, j]\n",
    "                elif len(p_l) == len(max_pl):\n",
    "                    if i < max_i[0]:\n",
    "                        max_pl = p_l\n",
    "                        max_i = [i, j]\n",
    "                    elif i == max_i[0]:\n",
    "                        if j < max_i[1]:\n",
    "                            max_pl = p_l\n",
    "                            max_i = [i, j]\n",
    "        return max_i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        n = len(points)\n",
    "        maxnum = 0\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            x,y = points[i]\n",
    "            val = collections.defaultdict(list)\n",
    "            for j in range(i+1,n):\n",
    "                xj,yj = points[j]\n",
    "                if xj==x:\n",
    "                    val[inf].append(j)\n",
    "                else:\n",
    "                    tmp = (yj-y)/(xj-x)\n",
    "                    val[tmp].append(j)\n",
    "            for c in val:\n",
    "                if len(val[c])+1>maxnum:\n",
    "                    ans = [i]+val[c]\n",
    "                    maxnum = len(ans)\n",
    "        return ans[:2]\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        ansnum=0\n",
    "        ans=[]\n",
    "        for i in range(len(points)):\n",
    "            x,y=points[i]\n",
    "            dict=defaultdict(list)\n",
    "            for j in range(i+1,len(points)):\n",
    "                tx,ty=points[j]\n",
    "                if tx-x==0:\n",
    "                    dict[\"inf\"].append(j)\n",
    "                else:\n",
    "                    k=(ty-y)/(tx-x)\n",
    "                    dict[k].append(j)\n",
    "            for k in dict:\n",
    "                if len(dict[k])+1>ansnum:\n",
    "                    ans=[i]+dict[k]\n",
    "                    ansnum=len(dict[k])+1\n",
    "        return ans[0:2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "\n",
    "        \"\"\"\n",
    "        双重循环，当固定一个点i时，只需计算其他点j与固定点i的斜率，用哈希表(key为斜率，value为斜率相同的点集构成的数组)将斜率相同的点记录下来。当斜率相同时，证明这些点都在一条直线上。\n",
    "        每次固定一个点i时，找到在同一斜率上点数最多的点的数组记录下来\n",
    "        已经计算过的点i不必再次计算，因为如果先计算别的点，同一直线上的点数也不会发生变化。\n",
    "        \"\"\"\n",
    "\n",
    "        n = len(points)\n",
    "\n",
    "        max_len = 0\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "\n",
    "            x1, y1 = points[i]\n",
    "            lookup = {}\n",
    "            for j in range(i+1, n):\n",
    "                x2,y2 = points[j]\n",
    "                if x2 == x1: # 斜率无穷大的直线\n",
    "                    if \"inf\" not in lookup:\n",
    "                        lookup[\"inf\"] = []\n",
    "                    lookup[\"inf\"].append(j)\n",
    "                else:\n",
    "                    k = (y2-y1)/(x2-x1)\n",
    "                    if k not in lookup:\n",
    "                        lookup[k] = []\n",
    "                    lookup[k].append(j)\n",
    "\n",
    "            for v in lookup.values():\n",
    "                if len(v)+1 > max_len:\n",
    "                    max_len = len(v) + 1\n",
    "                    res = [i] + v\n",
    "            \n",
    "        return res[0:2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        ansnum=0\n",
    "        ans=[]\n",
    "        for i in range(len(points)):\n",
    "            x,y=points[i]\n",
    "            dict=defaultdict(list)\n",
    "            for j in range(i+1,len(points)):\n",
    "                tx,ty=points[j]\n",
    "                if tx-x==0:\n",
    "                    dict[\"inf\"].append(j)\n",
    "                else:\n",
    "                    k=(ty-y)/(tx-x)\n",
    "                    dict[k].append(j)\n",
    "            for k in dict:\n",
    "                if len(dict[k])+1>ansnum:\n",
    "                    ans=[i]+dict[k]\n",
    "                    ansnum=len(dict[k])+1\n",
    "        return ans[0:2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        ansnum = 0\n",
    "        ans = []\n",
    "        for i in range(len(points)-1):\n",
    "            x, y = points[i]\n",
    "            dict = defaultdict(list)\n",
    "            for j in range(i+1, len(points)):\n",
    "                tx, ty = points[j]\n",
    "                if tx-x == 0:\n",
    "                    dict[\"inf\"].append(j)\n",
    "                else:\n",
    "                    k = (ty-y)/(tx-x)\n",
    "                    dict[k].append(j)\n",
    "            for value in dict.values():\n",
    "                if len(value) > ansnum:\n",
    "                    ansnum = len(value)\n",
    "                    ans.clear()\n",
    "                    ans = [i]+value\n",
    "        return ans[0:2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def bestLine(self, points):\n",
    "        max_len = 0\n",
    "        ans = []\n",
    "        for i in range(len(points)):\n",
    "            x1,y1 = points[i]\n",
    "            dict_k = defaultdict(list)\n",
    "            for j in range(i+1,len(points)):\n",
    "                x2,y2 = points[j]\n",
    "                if x1==x2:\n",
    "                    dict_k[float('inf')].append(j)\n",
    "                else:\n",
    "                    k = (y2-y1) / (x2-x1)\n",
    "                    dict_k[k].append(j)\n",
    "            \n",
    "            for k in dict_k.keys():\n",
    "                if len(dict_k[k])+1 > max_len:\n",
    "                    max_len = max(max_len,len(dict_k[k])+1)\n",
    "                    ans = [i] + dict_k[k]\n",
    "        \n",
    "        return ans[0:2]\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        ans = 0\n",
    "        res = []\n",
    "        for i in range(len(points)):\n",
    "            x,y = points[i]\n",
    "\n",
    "            dic = defaultdict(list)\n",
    "            for j in range(i+1,len(points)):\n",
    "                tx,ty = points[j]\n",
    "                if tx == x:\n",
    "                    dic['inf'].append(j)\n",
    "                else:\n",
    "                    k = (ty-y)/(tx-x)\n",
    "                    dic[k].append(j)\n",
    "            \n",
    "            for k in dic:\n",
    "                if len(dic[k]) + 1 > ans:\n",
    "                    res = [i] + dic[k]\n",
    "                    ans = len(dic[k]) + 1\n",
    "        return res[:2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        # points.sort(key = lambda x :(x[0],x[1]))\n",
    "        def gcd(a,b):\n",
    "            return a if b==0 else gcd(b,a%b)\n",
    "        ans = [0,1]\n",
    "        maxPoint = 2\n",
    "        n = len(points)\n",
    "        for i in range(n):\n",
    "            if n-i<=maxPoint:\n",
    "                break\n",
    "            line = {}\n",
    "            for j in range(i+1,n):\n",
    "                a = points[j][1] - points[i][1]\n",
    "                b = points[i][0] - points[j][0]\n",
    "                c = points[j][0]*points[i][1] - points[j][1]*points[i][0]\n",
    "                m = gcd(gcd(a,b),c)\n",
    "                a/=m\n",
    "                b/=m\n",
    "                c/=m\n",
    "                if (a,b,c) not in line:\n",
    "                    line[(a,b,c)] = [2,i,j]\n",
    "                else:\n",
    "                    line[(a,b,c)][0]+=1\n",
    "                    if (line[(a,b,c)][0]>maxPoint) or (line[(a,b,c)][0]==maxPoint and (line[(a,b,c)][1]<ans[0] or (line[(a,b,c)][1]==ans[0] and line[(a,b,c)][2]<ans[1]))):\n",
    "                        maxPoint = line[(a,b,c)][0]\n",
    "                        ans = line[(a,b,c)][1:]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        def method(dic,k):\n",
    "            if dic.get(k)==None:\n",
    "                dic[k]=[]\n",
    "        max_num=0\n",
    "        result=[None,None]\n",
    "        for i in range(len(points)):\n",
    "            x,y=points[i]\n",
    "            dic={}\n",
    "            for j in range(i+1,len(points)):\n",
    "                tx,ty=points[j]\n",
    "                if tx-x==0:\n",
    "                    method(dic,\"inf\")\n",
    "                    dic[\"inf\"].append(j)\n",
    "                else:\n",
    "                    k=(ty-y)/(tx-x)\n",
    "                    method(dic, k)\n",
    "                    dic[k].append(j)\n",
    "\n",
    "            for k in dic.keys():\n",
    "                if len(dic[k])+1>max_num:\n",
    "                    max_num=len(dic[k])+1\n",
    "                    result=[i,dic[k][0]]\n",
    "        \n",
    "        return result\n",
    "\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        max_length = 2\n",
    "        ret = [0, 1]\n",
    "        for i, (x1, y1) in enumerate(points):\n",
    "            counter = dict()\n",
    "            for j in range(len(points)):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                a, b = points[j][0]-x1, points[j][1]-y1\n",
    "                c = gcd(a, b)\n",
    "                k = (a//c, b//c)\n",
    "                if k not in counter:\n",
    "                    counter[k] = list()\n",
    "                if j > i and (not counter[k] or counter[k][-1] < i):\n",
    "                    counter[k].append(i)\n",
    "                counter[k].append(j)\n",
    "\n",
    "            for k in counter:\n",
    "                if len(counter[k]) < max_length:\n",
    "                    continue\n",
    "                elif len(counter[k]) > max_length:\n",
    "                    ret = counter[k][:2]\n",
    "                    max_length = len(counter[k])\n",
    "                else:\n",
    "                    ret = min(ret, counter[k][:2])\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        res=0\n",
    "        ans=[]\n",
    "        \n",
    "        n=len(points)\n",
    "        for i in range(n):\n",
    "            xi,yi=points[i]\n",
    "            hashmap=defaultdict(list)\n",
    "            for j in range(i+1,n):\n",
    "                xj,yj=points[j]\n",
    "                if xj-xi==0:\n",
    "                    hashmap['inf'].append(j)\n",
    "                else:\n",
    "                    k=(yj-yi)/(xj-xi)\n",
    "                    hashmap[k].append(j)\n",
    "            for k in hashmap:\n",
    "                if len(hashmap[k])+1>res:\n",
    "                    ans=[i]+hashmap[k]\n",
    "                    res=len(hashmap[k])+1\n",
    "        return ans[0:2]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        res = [0, 0]\n",
    "        tmp = 0\n",
    "        for i in range(len(points)):\n",
    "            data = collections.defaultdict(list)\n",
    "            for j in range(i+1, len(points)):\n",
    "                if points[j][0] - points[i][0] == 0:\n",
    "                    data[\"inf\"].append(j)\n",
    "                else:\n",
    "                    k = (points[j][1] - points[i][1]) / (points[j][0] - points[i][0])\n",
    "                    data[k].append(j)\n",
    "            \n",
    "            \n",
    "            for k in data:\n",
    "                if len(data[k]) > tmp:\n",
    "                    tmp = len(data[k])\n",
    "                    res = [i, data[k][0]]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        max_length = 2\n",
    "        ret = [0, 1]\n",
    "        for i, (x1, y1) in enumerate(points):\n",
    "            counter = dict()\n",
    "            for j in range(len(points)):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                a, b = points[j][0]-x1, points[j][1]-y1\n",
    "                c = gcd(a, b)\n",
    "                k = (a//c, b//c)\n",
    "                if k not in counter:\n",
    "                    counter[k] = list()\n",
    "                if j > i and (not counter[k] or counter[k][-1] < i):\n",
    "                    counter[k].append(i)\n",
    "                counter[k].append(j)\n",
    "\n",
    "            for k in counter:\n",
    "                if len(counter[k]) < max_length:\n",
    "                    continue\n",
    "                elif len(counter[k]) > max_length:\n",
    "                    ret = counter[k][:2]\n",
    "                    max_length = len(counter[k])\n",
    "                else:\n",
    "                    ret = min(ret, counter[k][:2])\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        max_length = 2\n",
    "        ret = [0, 1]\n",
    "        for i, (x1, y1) in enumerate(points):\n",
    "            counter = dict()\n",
    "            for j in range(len(points)):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                a, b = points[j][0]-x1, points[j][1]-y1\n",
    "                c = gcd(a, b)\n",
    "                k = (a//c, b//c)\n",
    "                if k not in counter:\n",
    "                    counter[k] = list()\n",
    "                if j > i and (not counter[k] or counter[k][-1] < i):\n",
    "                    counter[k].append(i)\n",
    "                counter[k].append(j)\n",
    "\n",
    "            for k in counter:\n",
    "                if len(counter[k]) < max_length:\n",
    "                    continue\n",
    "                elif len(counter[k]) > max_length:\n",
    "                    ret = counter[k][:2]\n",
    "                    max_length = len(counter[k])\n",
    "                else:\n",
    "                    ret = min(ret, counter[k][:2])\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        ansnum=0\n",
    "        ans=[]\n",
    "        for i in range(len(points)):\n",
    "            x,y=points[i]\n",
    "            dict=defaultdict(list)\n",
    "            for j in range(i+1,len(points)):\n",
    "                tx,ty=points[j]\n",
    "                if tx-x==0:\n",
    "                    dict[\"inf\"].append(j)\n",
    "                else:\n",
    "                    k=(ty-y)/(tx-x)\n",
    "                    dict[k].append(j)\n",
    "            for k in dict:\n",
    "                if len(dict[k])+1>ansnum:\n",
    "                    ans=[i]+dict[k]\n",
    "                    ansnum=len(dict[k])+1\n",
    "        return ans[0:2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        ansnum=0\n",
    "        ans=[]\n",
    "        for i in range(len(points)):\n",
    "            x,y=points[i]\n",
    "            dict=defaultdict(list)\n",
    "            for j in range(i+1,len(points)):\n",
    "                tx,ty=points[j]\n",
    "                if tx-x==0:\n",
    "                    dict[\"inf\"].append(j)\n",
    "                else:\n",
    "                    k=(ty-y)/(tx-x)\n",
    "                    dict[k].append(j)\n",
    "            for k in dict:\n",
    "                if len(dict[k])+1>ansnum:\n",
    "                    ans=[i]+dict[k]\n",
    "                    ansnum=len(dict[k])+1\n",
    "        return ans[0:2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(len(points)):\n",
    "            x,y = points[i]\n",
    "            dict = defaultdict(list)\n",
    "            for j in range(i+1,len(points)):\n",
    "                tx,ty = points[j]\n",
    "                # 斜率不存在\n",
    "                if tx - x == 0:\n",
    "                    dict[\"inf\"].append(j)\n",
    "                else:\n",
    "                    k = (ty-y)/(tx-x)\n",
    "                    dict[k].append(j)\n",
    "            for k, v in dict.items():\n",
    "                if len(v)+1 > len(res):\n",
    "                    res = [i] + v\n",
    "        return res[0:2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        ansnum=0\n",
    "        ans=[]\n",
    "        for i in range(len(points)):\n",
    "            x,y=points[i]\n",
    "            dict=defaultdict(list)\n",
    "            for j in range(i+1,len(points)):\n",
    "                tx,ty=points[j]\n",
    "                if tx-x==0:\n",
    "                    dict[\"inf\"].append(j)\n",
    "                else:\n",
    "                    k=(ty-y)/(tx-x)\n",
    "                    dict[k].append(j)\n",
    "            for k in dict:\n",
    "                if len(dict[k])+1>ansnum:\n",
    "                    ans=[i]+dict[k]\n",
    "                    ansnum=len(dict[k])+1\n",
    "        return ans[0:2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        ans = 0\n",
    "        res = []\n",
    "\n",
    "        n = len(points)\n",
    "\n",
    "        for i in range(n):\n",
    "            x,y = points[i]\n",
    "            dic = defaultdict(list)\n",
    "            for j in range(i+1,n):\n",
    "                tx,ty = points[j]\n",
    "\n",
    "                if tx == x:\n",
    "                    dic['inf'].append(j)\n",
    "                else:\n",
    "                    k = (y-ty)/(x-tx)\n",
    "\n",
    "                    dic[k].append(j)\n",
    "\n",
    "            for k in dic:\n",
    "                if len(dic[k]) + 1 > ans:\n",
    "                    res = [i] + dic[k]\n",
    "                    ans = len(dic[k]) + 1\n",
    "        return res[:2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        ansnum=0\n",
    "        ans=[]\n",
    "        for i in range(len(points)):\n",
    "            x,y=points[i]\n",
    "            dict=defaultdict(list)\n",
    "            for j in range(i+1,len(points)):\n",
    "                tx,ty=points[j]\n",
    "                if tx-x==0:\n",
    "                    dict[\"inf\"].append(j)\n",
    "                else:\n",
    "                    k=(ty-y)/(tx-x)\n",
    "                    dict[k].append(j)\n",
    "            for k in dict:\n",
    "                if len(dict[k])+1>ansnum:\n",
    "                    ans=[i]+dict[k]\n",
    "                    ansnum=len(dict[k])+1\n",
    "        return ans[0:2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        # 计算斜率,并将斜率存在哈希表表中，其中键是斜率，值是对应的位置\n",
    "        ansnum = 0\n",
    "        ans = []\n",
    "        for i  in range(len(points)):\n",
    "            x,y = points[i]\n",
    "            d = defaultdict(list)\n",
    "            for j in range(i+1, len(points)):\n",
    "                tx, ty = points[j]\n",
    "                if x==tx:\n",
    "                    d[\"inf\"].append(j)\n",
    "                else:\n",
    "                    k = (ty-y)/(tx-x)\n",
    "                    d[k].append(j)\n",
    "            # 求出i点最多的斜率\n",
    "            for k in d:\n",
    "                if len(d[k])+1>ansnum:\n",
    "                    ans = [i]+d[k]\n",
    "                    ansnum = len(d[k])+1\n",
    "        return ans[0:2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        n = len(points)\n",
    "        maxnum = 0\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            x,y = points[i]\n",
    "            val = collections.defaultdict(list)\n",
    "            for j in range(i+1,n):\n",
    "                xj,yj = points[j]\n",
    "                if xj==x:\n",
    "                    val[inf].append(j)\n",
    "                else:\n",
    "                    tmp = (yj-y)/(xj-x)\n",
    "                    val[tmp].append(j)\n",
    "            for c in val:\n",
    "                if len(val[c])+1>maxnum:\n",
    "                    ans = [i]+val[c]\n",
    "                    maxnum = len(ans)\n",
    "        return ans[:2]\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        ansnum=0\n",
    "        ans=[]\n",
    "        for i in range(len(points)):\n",
    "            x,y=points[i]\n",
    "            dict=defaultdict(list)\n",
    "            for j in range(i+1,len(points)):\n",
    "                tx,ty=points[j]\n",
    "                if tx-x==0:\n",
    "                    dict[\"inf\"].append(j)\n",
    "                else:\n",
    "                    k=(ty-y)/(tx-x)\n",
    "                    dict[k].append(j)\n",
    "            for k in dict:\n",
    "                if len(dict[k])+1>ansnum:\n",
    "                    ans=[i]+dict[k]\n",
    "                    ansnum=len(dict[k])+1\n",
    "        return ans[0:2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        ansnum = 0  # 用于存储直线穿过的最多点数\n",
    "        ans = []  # 用于存储结果\n",
    "        \n",
    "        for i in range(len(points)):\n",
    "            x, y = points[i]\n",
    "            dict = defaultdict(list)  # 初始化一个空的哈希表\n",
    "            \n",
    "            for j in range(i + 1, len(points)):\n",
    "                tx, ty = points[j]\n",
    "                \n",
    "                if tx - x == 0:  # 处理垂直线的情况\n",
    "                    dict[\"inf\"].append(j)\n",
    "                else:  # 计算斜率并存储\n",
    "                    k = (ty - y) / (tx - x)\n",
    "                    dict[k].append(j)\n",
    "            \n",
    "            # 更新穿过最多点的直线\n",
    "            for k in dict:\n",
    "                if len(dict[k]) + 1 > ansnum:\n",
    "                    ans = [i] + dict[k]\n",
    "                    ansnum = len(dict[k]) + 1\n",
    "        \n",
    "        return ans[0:2]  # 返回结果的前两个元素，即S[0]和S[1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "       \n",
    "        import collections\n",
    "\n",
    "\n",
    "        length = 0 #记录最大长度\n",
    "\n",
    "        # hs ,key为固定的i点，value为与当前i点相同斜率的点\n",
    "        ans=[]\n",
    "        for i in range(len(points)):\n",
    "            x,y=points[i]\n",
    "            hs = collections.defaultdict(list)\n",
    "            for j in range(i+1,len(points)):\n",
    "                tempx,tempy = points[j]\n",
    "                if tempx-x == 0:\n",
    "                    hs['inf'].append(j)\n",
    "                else:\n",
    "                    hs[(tempy-y)/(tempx-x)].append(j)\n",
    "\n",
    "            for k in hs:\n",
    "                if len(hs[k])>length:\n",
    "                    ans=[i]+hs[k]\n",
    "                    length=len(hs[k])\n",
    "\n",
    "        return ans[0:2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        mx = 0\n",
    "        ans = []\n",
    "        for i in range(len(points)):\n",
    "            x , y = points[i]\n",
    "            dict = defaultdict(list)\n",
    "            for j in range(i + 1, len(points)):\n",
    "                tx, ty = points[j]\n",
    "                if tx - x == 0:\n",
    "                    dict[\"inf\"].append(j)\n",
    "                else:\n",
    "                    k = (ty - y) / (tx - x)\n",
    "                    dict[k].append(j)\n",
    "            for k in dict:\n",
    "                if len(dict[k]) + 1 > mx:\n",
    "                    ans = [i] + dict[k]\n",
    "                    mx = len(dict[k]) + 1\n",
    "        return ans[0:2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        max_l = 0\n",
    "        res = [0,1]\n",
    "        for i in range(len(points)-1):\n",
    "            ls = defaultdict(list)\n",
    "            for j in range(i+1, len(points)):\n",
    "                dx, dy = points[j][0] - points[i][0], points[j][1] - points[i][1]\n",
    "                k = dy/dx if dx != 0 else math.inf\n",
    "                ls[(i,k)].append(j)\n",
    "            for v in ls.values():\n",
    "                if len(v) > max_l:\n",
    "                    max_l = len(v)\n",
    "                    res = [i,v[0]]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "         # time O(n^2), space O(n)\n",
    "        n = len(points)\n",
    "        res = []\n",
    "        max_cnt = 1\n",
    "        for i in range(n - 1):  # For a fixed point points[i], consider all other points points[j]\n",
    "            indices = collections.defaultdict(list)  # 斜率 -> 斜率相同的点的下标\n",
    "            for j in range(i + 1, n): # j != i, start from i + 1 by avoid calculating same pairs of points\n",
    "                indices[self.getAngle(points[i], points[j])].append(j)\n",
    "            for slope in indices.keys(): # 对于每个固定的点i，找到在同一斜率slope上点数最多的点的下标\n",
    "                if len(indices[slope]) + 1 > max_cnt:\n",
    "                    max_cnt = len(indices[slope]) + 1\n",
    "                    res = [i] + indices[slope]\n",
    "        return res[:2]  # 返回这条直线的前两个点\n",
    "\n",
    "    def getAngle(self, point1, point2):\n",
    "        if point1[0] == point2[0]:  # vertical line \n",
    "            return math.inf\n",
    "        else:\n",
    "            return (point1[1] - point2[1]) / (point1[0] - point2[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef bestLine(self, points):\n",
    "\t\tn = len(points)\n",
    "\t\tmx = 0\n",
    "\t\tvisited = set()\n",
    "\t\tfor i in range(n):\n",
    "\t\t\tx0, y0 = points[i]\n",
    "\t\t\tfor j in range(i + 1, n):\n",
    "\t\t\t\tif n - j + 1 <= mx:\n",
    "\t\t\t\t\tbreak\n",
    "\t\t\t\tif (i, j) in visited:\n",
    "\t\t\t\t\tcontinue\n",
    "\t\t\t\tx1, y1 = points[j]\n",
    "\t\t\t\tcnt = 2\n",
    "\t\t\t\tfor k in range(j + 1, n):\n",
    "\t\t\t\t\tif (points[k][0] - x1) * (y1 - y0) == (points[k][1] - y1) * (x1 - x0):\n",
    "\t\t\t\t\t\tcnt += 1\n",
    "\t\t\t\t\t\tvisited.add((i, k))\n",
    "\t\t\t\t\t\tvisited.add((j, k))\n",
    "\t\t\t\tif cnt > mx:\n",
    "\t\t\t\t\tmx = cnt\n",
    "\t\t\t\t\tans = [i, j]\n",
    "\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef bestLine(self, points):\n",
    "\t\tn = len(points)\n",
    "\t\tmx = 0\n",
    "\t\tvisited = set()\n",
    "\t\tfor i in range(n):\n",
    "\t\t\tx0, y0 = points[i]\n",
    "\t\t\tfor j in range(i + 1, n):\n",
    "\t\t\t\tif (i, j) in visited:\n",
    "\t\t\t\t\tcontinue\n",
    "\t\t\t\tx1, y1 = points[j]\n",
    "\t\t\t\tcnt = 2\n",
    "\t\t\t\tfor k in range(j + 1, n):\n",
    "\t\t\t\t\tif (points[k][0] - x1) * (y1 - y0) == (points[k][1] - y1) * (x1 - x0):\n",
    "\t\t\t\t\t\tcnt += 1\n",
    "\t\t\t\t\t\tvisited.add((i, k))\n",
    "\t\t\t\t\t\tvisited.add((j, k))\n",
    "\t\t\t\tif cnt > mx:\n",
    "\t\t\t\t\tmx = cnt\n",
    "\t\t\t\t\tans = [i, j]\n",
    "\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        n = len(points)\n",
    "        res = 0\n",
    "        pt = 0\n",
    "        num = []\n",
    "        xielv = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            [x1, y1] = points[i]\n",
    "            for j in range(i + 1, n):\n",
    "                [x2, y2] = points[j]\n",
    "                k = None if x1 == x2 else (y2 - y1) / (x2 - x1)\n",
    "                xielv[i][j] = xielv[j][i] = k\n",
    "        # print(xielv)\n",
    "        for i, line in enumerate(xielv):\n",
    "            cnt = Counter(line)\n",
    "            cnt[0] -= 1\n",
    "            tmp = max(cnt.values())\n",
    "            if tmp > res:\n",
    "                res = tmp\n",
    "                num = []\n",
    "                for k, v in cnt.items():\n",
    "                    if v == res:\n",
    "                        num.append(k)\n",
    "                pt = i\n",
    "        for i in range(n):\n",
    "            if i != pt and xielv[pt][i] in num:\n",
    "                return [pt, i]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        n = len(points)\n",
    "        if n <= 2:\n",
    "            return n\n",
    "        dy = [[0] * n for _ in range(n)]\n",
    "        dx = [[0] * n for _ in range(n)]\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                dx[i][j] = points[j][0] - points[i][0]\n",
    "                dy[i][j] = points[j][1] - points[i][1]\n",
    "        max_points = 2\n",
    "        visited = [[False] * n for _ in range(n)]\n",
    "        result = [0, 1]\n",
    "        for i in range(n - 2):\n",
    "            for j in range(i + 1, n - 1):\n",
    "                if visited[i][j]:\n",
    "                    continue\n",
    "                num_points = 2\n",
    "                line_points = []\n",
    "                for k in range(j + 1, n):\n",
    "                    if dy[i][j] * dx[j][k] == dy[j][k] * dx[i][j]:\n",
    "                        num_points += 1\n",
    "                        line_points.append(k)\n",
    "                for p in line_points:\n",
    "                    visited[j][p] = True\n",
    "                for p1 in range(len(line_points) - 1):\n",
    "                    for p2 in range(p1 + 1, len(line_points)):\n",
    "                        visited[line_points[p1]][line_points[p2]] = True\n",
    "                if num_points > max_points:\n",
    "                    max_points = num_points\n",
    "                    result = [i, j]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        ls = {}\n",
    "        for i in range(len(points)-1):\n",
    "            lsi = {}\n",
    "            psi = {}\n",
    "            for j in range(i+1, len(points)):\n",
    "                dx, dy = points[j][0] - points[i][0], points[j][1] - points[i][1]\n",
    "                k = dy/dx if dx != 0 else math.inf\n",
    "                if k in lsi:\n",
    "                    lsi[k] += 1\n",
    "                else:\n",
    "                    psi[(i,j)] = k\n",
    "                    lsi[k] = 2\n",
    "            for k,v in psi.items():\n",
    "                ls[k] = lsi[v]\n",
    "        max_l = max(ls.values())\n",
    "        ps = [k for k,v in ls.items() if v==max_l]\n",
    "        ps.sort()\n",
    "        return list(ps[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        ls = {}\n",
    "        for i in range(len(points)-1):\n",
    "            lsi = {}\n",
    "            psi = {}\n",
    "            for j in range(i+1, len(points)):\n",
    "                dx, dy = points[j][0] - points[i][0], points[j][1] - points[i][1]\n",
    "                k = dy/dx if dx != 0 else math.inf\n",
    "                print(i,j, dx, dy)\n",
    "                if k in lsi:\n",
    "                    lsi[k] += 1\n",
    "                else:\n",
    "                    psi[(i,j)] = k\n",
    "                    lsi[k] = 2\n",
    "            for k,v in psi.items():\n",
    "                ls[k] = lsi[v]\n",
    "        max_l = max(ls.values())\n",
    "        ps = [k for k,v in ls.items() if v==max_l]\n",
    "        ps.sort()\n",
    "        return list(ps[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        INF = float(\"inf\")\n",
    "        N = len(points)\n",
    "        kMap = defaultdict(list)\n",
    "        # points.sort()\n",
    "        from fractions import Fraction \n",
    "\n",
    "        for i in range(N):\n",
    "            x1,y1 = points[i]\n",
    "            for j in range(i+1,N):\n",
    "                x2,y2 = points[j]\n",
    "                k = Fraction(y2-y1,x2-x1) if x2-x1!=0 else INF \n",
    "                if (i,k) not in kMap:\n",
    "                    kMap[(i,k)]=[j,1]\n",
    "                else:\n",
    "                    kMap[(i,k)][0] = min(kMap[(i,k)][0],j)\n",
    "                    kMap[(i,k)][1] += 1\n",
    "        mCnt = 0\n",
    "        mi,mj = 0,0\n",
    "        for i,k in kMap:\n",
    "            if kMap[(i,k)][1]>=mCnt:\n",
    "                if kMap[(i,k)][1]==mCnt and (i>mi or (i==mi and j>mj)):\n",
    "                    pass\n",
    "                else:\n",
    "                    mi = i\n",
    "                    mj = kMap[(i,k)][0]\n",
    "                mCnt = kMap[(i,k)][1]\n",
    "        # print(mCnt,kMap)\n",
    "        return [mi,mj]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# math question, copied\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        d = {}\n",
    "        x = y = 0\n",
    "        maxCount = 0\n",
    "        for i in range(len(points)):\n",
    "            for j in range(i+1, len(points)):\n",
    "                k, b = self.f([points[i], points[j]])\n",
    "                if (k, b) in d.keys():\n",
    "                    d[(k, b)][0] += 1\n",
    "                else:\n",
    "                    d[(k, b)] = [1, (i, j)]\n",
    "                if d[(k, b)][0] > maxCount or (d[(k, b)][0] == maxCount and d[(k, b)][1][0] < x) or (d[(k, b)][0] == maxCount and d[(k, b)][1][0] == x and d[(k, b)][1][1] < y):\n",
    "                    maxCount = d[(k, b)][0]\n",
    "                    x, y = d[(k, b)][1]\n",
    "                print(x, y)\n",
    "        return [x, y]\n",
    "\n",
    "    # 求两点之间连线的斜率k和截距b\n",
    "    def f(self, points: List[List[int]]) -> List[int]:\n",
    "        if points[0][0] == points[1][0]:\n",
    "            return [float('inf'), points[0][0]]\n",
    "        else:\n",
    "            return [(points[1][1]-points[0][1]) / (points[1][0]-points[0][0]),\n",
    "            (points[0][1]*points[1][0]-points[1][1]*points[0][0]) / (points[1][0]-points[0][0])]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        if len(points)==2:\n",
    "            return [0,1]\n",
    "        else:\n",
    "            dicc={}\n",
    "            maxx=-1\n",
    "            s0=-1\n",
    "            s1=-1\n",
    "            for i in range(len(points)-1):\n",
    "                for j in range(i+1,len(points)):\n",
    "                    if points[j][0]-points[i][0]==0:\n",
    "                        xielv=float('inf')\n",
    "                        jieju=points[i][0]\n",
    "                    else:\n",
    "                        xielv=(float)(points[j][1]-points[i][1])/(points[j][0]-points[i][0])\n",
    "                        jieju=points[i][1]-xielv*points[i][0]\n",
    "                    comb=(xielv,jieju)\n",
    "                    a=\"\"\n",
    "                    if not comb in dicc:\n",
    "                        dicc[comb]=[2,[i,j]]\n",
    "                        a=[i,j]\n",
    "                    else:\n",
    "                        a=dicc[comb][1]\n",
    "                        a.append(i)\n",
    "                        a.append(j)\n",
    "                        a=list(set(a))\n",
    "                        a=sorted(a)\n",
    "                        dicc[comb]=[len(a),a]\n",
    "                    if(len(a))>maxx:\n",
    "                        maxx=len(a)\n",
    "                        s0=a[0]\n",
    "                        s1=a[1]\n",
    "                    elif (len(a))==maxx:\n",
    "                        if a[0]<s0:\n",
    "                            s0=a[0]\n",
    "                            s1=a[1]\n",
    "                        elif a[0]==s0:\n",
    "                            if a[1]<s1:\n",
    "                                s0=a[0]\n",
    "                                s1=a[1]\n",
    "            return [s0,s1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        ls = defaultdict(list)\n",
    "        for i in range(len(points)-1):\n",
    "            for j in range(i+1, len(points)):\n",
    "                dx, dy = points[j][0] - points[i][0], points[j][1] - points[i][1]\n",
    "                k = dy/dx if dx != 0 else math.inf\n",
    "                ls[(i,k)].append(j)\n",
    "        ps = sorted([[-len(v), k[0], v[0]] for k,v in ls.items()])\n",
    "        return ps[0][1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        lines_dict = {}\n",
    "\n",
    "        n = len(points)\n",
    "        for i in range(1, n):\n",
    "            slopes = set()\n",
    "            for j in range(i):\n",
    "                if points[i][0] - points[j][0]:\n",
    "                    slope = (points[i][1] - points[j][1]) / (points[i][0] - points[j][0])\n",
    "                else:\n",
    "                    slope = float(\"inf\")\n",
    "                if slope != 0 and slope != float(\"inf\"):\n",
    "                    cut = - points[j][1] / slope  \n",
    "                elif slope == 0:\n",
    "                    cut = points[j][1]\n",
    "                else:\n",
    "                    cut = points[j][0]\n",
    "                if slope in slopes:\n",
    "                    continue\n",
    "\n",
    "                slopes.add(slope)\n",
    "                if (slope, cut) in lines_dict:\n",
    "                    lines_dict[(slope, cut)].append(i)\n",
    "                else:\n",
    "                    lines_dict[(slope, cut)] = [j, i]\n",
    "        \n",
    "        import heapq\n",
    "        hq = []\n",
    "        for k in lines_dict:\n",
    "            heapq.heappush(hq, [-len(lines_dict[k]), lines_dict[k][0], lines_dict[k][1]])\n",
    "    \n",
    "        return hq[0][1:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        lines_dict = {}\n",
    "\n",
    "        n = len(points)\n",
    "        for i in range(1, n):\n",
    "            slopes = set()\n",
    "            for j in range(i):\n",
    "                if points[i][0] - points[j][0]:\n",
    "                    slope = (points[i][1] - points[j][1]) / (points[i][0] - points[j][0])\n",
    "                else:\n",
    "                    slope = float(\"inf\")\n",
    "                if slope != 0 and slope != float(\"inf\"):\n",
    "                    cut = - points[j][1] / slope  \n",
    "                elif slope == 0:\n",
    "                    cut = points[j][1]\n",
    "                else:\n",
    "                    cut = points[j][0]\n",
    "                if slope in slopes:\n",
    "                    continue\n",
    "\n",
    "                slopes.add(slope)\n",
    "                if (slope, cut) in lines_dict:\n",
    "                    lines_dict[(slope, cut)].append(i)\n",
    "                else:\n",
    "                    lines_dict[(slope, cut)] = [j, i]\n",
    "        \n",
    "        import heapq\n",
    "        hq = []\n",
    "        for k in lines_dict:\n",
    "            heapq.heappush(hq, [-len(lines_dict[k]), lines_dict[k][0], lines_dict[k][1]])\n",
    "    \n",
    "        return hq[0][1:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        ls = defaultdict(list)\n",
    "        for i in range(len(points)-1):\n",
    "            for j in range(i+1, len(points)):\n",
    "                dx, dy = points[j][0] - points[i][0], points[j][1] - points[i][1]\n",
    "                k = dy/dx if dx != 0 else math.inf\n",
    "                ls[(i,k)].append(j)\n",
    "        print(ls)\n",
    "        ps = sorted([[-len(v), k[0], v[0]] for k,v in ls.items()])\n",
    "        return ps[0][1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        ls = defaultdict(list)\n",
    "        for i in range(len(points)-1):\n",
    "            for j in range(i+1, len(points)):\n",
    "                dx, dy = points[j][0] - points[i][0], points[j][1] - points[i][1]\n",
    "                k = dy/dx if dx != 0 else math.inf\n",
    "                ls[(i,k)].append(j)\n",
    "        print(ls)\n",
    "        ps = sorted([[-len(v), k[0], v[0]] for k,v in ls.items()])\n",
    "        return ps[0][1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        n = len(points)\n",
    "        lines = {}\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                dx, dy = points[j][0] - points[i][0], points[j][1] - points[i][1]\n",
    "                vec = None\n",
    "                if dx == 0:\n",
    "                    vec = (math.inf, -points[i][0])\n",
    "                else:\n",
    "                    k = dy / dx\n",
    "                    vec = (k, points[i][1] - k * points[i][0])\n",
    "                lines.setdefault(vec, set())\n",
    "                lines[vec].add(i)\n",
    "                lines[vec].add(j)\n",
    "        for line in lines:\n",
    "            lines[line] = list(sorted(lines[line]))\n",
    "        return lines[max(lines, key=lambda x: (len(lines[x]), -lines[x][0], -lines[x][1]))][:2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        n = len(points)\n",
    "        lines = {}\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                dx, dy = points[j][0] - points[i][0], points[j][1] - points[i][1]\n",
    "                vec = None\n",
    "                if dx == 0:\n",
    "                    vec = (math.inf, -points[i][0])\n",
    "                else:\n",
    "                    k = dy / dx\n",
    "                    vec = (k, points[i][1] - k * points[i][0])\n",
    "                lines.setdefault(vec, set())\n",
    "                lines[vec].add(i)\n",
    "                lines[vec].add(j)\n",
    "        for line in lines:\n",
    "            lines[line] = list(sorted(lines[line]))\n",
    "        return lines[max(lines, key=lambda x: (len(lines[x]), -lines[x][0], -lines[x][1]))][:2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        n = len(points)\n",
    "        def func(x,y):\n",
    "            if x[0]==y[0]:\n",
    "                k,b = inf,x[0]\n",
    "            else:\n",
    "                k = (y[1]-x[1])/(y[0]-x[0])\n",
    "                b = y[1]-k*y[0]\n",
    "            return (k,b)\n",
    "        acc = collections.defaultdict(set)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                tmp = func(points[i],points[j])\n",
    "                acc[tmp].add(i)\n",
    "                acc[tmp].add(j)\n",
    "        ans = list(acc.values())\n",
    "        ans.sort(key=lambda x:-len(x))\n",
    "        tmp = len(ans[0])\n",
    "        res = [inf,inf]\n",
    "        for i in range(len(ans)):\n",
    "            if len(ans[i])!=tmp:\n",
    "                break\n",
    "            re = sorted(list(ans[i]))\n",
    "            if re[0]<res[0] or (re[0]==res[0] and re[1]<res[1]):\n",
    "                res = re[:2]\n",
    "        return res\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        def line(x1, x2):\n",
    "            if x1[0] == x2[0]:\n",
    "                return (float('inf'), x1[0])\n",
    "            else:\n",
    "                k = (x2[1] - x1[1])/(x2[0] - x1[0])\n",
    "                b = (x2[0]*x1[1] - x1[0]*x2[1])/(x2[0] - x1[0])\n",
    "                return (k, b)\n",
    "        record = collections.defaultdict(set)\n",
    "        for i in range(len(points)):\n",
    "            for j in range(i):\n",
    "                record[line(points[j], points[i])].add(j)\n",
    "                record[line(points[j], points[i])].add(i)\n",
    "        \n",
    "        length = 0\n",
    "        res = 0\n",
    "        for key in record:\n",
    "            if len(record[key]) > length:\n",
    "                length = len(record[key])\n",
    "                res = record[key]\n",
    "        temp = []\n",
    "        for key in record:\n",
    "            if len(record[key]) == length:\n",
    "                temp.append(sorted(list(record[key])))\n",
    "        temp.sort(key = lambda x:(x[0], x[1]))\n",
    "        return temp[0][:2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        record = {}\n",
    "        for i in range(len(points)-1):\n",
    "            for j in range(i+1, len(points)):\n",
    "                y_dist = points[j][1] - points[i][1]\n",
    "                x_dist = points[j][0] - points[i][0]\n",
    "                if x_dist == 0:\n",
    "                    zero_y = float('inf')\n",
    "                    tangle = float('inf')\n",
    "                else:\n",
    "                    tangle = y_dist/x_dist\n",
    "                    zero_y = points[i][0] - (points[i][0] * tangle)\n",
    "                key = (zero_y, points[i][0], tangle)\n",
    "                if key not in record:\n",
    "                    record[key] = set()\n",
    "                record[key].add(i)\n",
    "                record[key].add(j)\n",
    "        max_len = 0\n",
    "        max_indexes = []\n",
    "        for value in record.values():\n",
    "            if len(value) > max_len:\n",
    "                max_indexes = [sorted(list(value))[:2]]\n",
    "                max_len = len(value)\n",
    "            elif len(value) == max_len:\n",
    "                max_indexes.append(sorted(list(value))[:2])\n",
    "        return sorted(max_indexes, key=lambda x: (x[0], x[1]))[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        n = len(points)\n",
    "        def func(x,y):\n",
    "            if x[0]==y[0]:\n",
    "                k,b = inf,x[0]\n",
    "            else:\n",
    "                k = (y[1]-x[1])/(y[0]-x[0])\n",
    "                b = y[1]-k*y[0]\n",
    "            return (k,b)\n",
    "        acc = collections.defaultdict(set)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                tmp = func(points[i],points[j])\n",
    "                acc[tmp].add(i)\n",
    "                acc[tmp].add(j)\n",
    "        # print(len(acc),acc)\n",
    "        ans = list(acc.values())\n",
    "        ans.sort(key=lambda x:-len(x))\n",
    "        tmp = len(ans[0])\n",
    "        res = [inf,inf]\n",
    "        for i in range(len(ans)):\n",
    "            if len(ans[i])!=tmp:\n",
    "                break\n",
    "            re = sorted(list(ans[i]))\n",
    "            if re[0]<res[0] or (re[0]==res[0] and re[1]<res[1]):\n",
    "                res = re[:2]\n",
    "        return res\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        n = len(points)\n",
    "        def func(x,y):\n",
    "            if x[0]==y[0]:\n",
    "                k,b = inf,x[0]\n",
    "            else:\n",
    "                k = (y[1]-x[1])/(y[0]-x[0])\n",
    "                b = y[1]-k*y[0]\n",
    "            return (k,b)\n",
    "        acc = collections.defaultdict(set)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                tmp = func(points[i],points[j])\n",
    "                acc[tmp].add(i)\n",
    "                acc[tmp].add(j)\n",
    "        ans = list(acc.values())\n",
    "        ans.sort(key=lambda x:-len(x))\n",
    "        tmp = len(ans[0])\n",
    "        res = [inf,inf]\n",
    "        for i in range(len(ans)):\n",
    "            if len(ans[i])!=tmp:\n",
    "                break\n",
    "            re = sorted(list(ans[i]))\n",
    "            if re[0]<res[0] or (re[0]==res[0] and re[1]<res[1]):\n",
    "                res = re[:2]\n",
    "        return res\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        record = {}\n",
    "        for i in range(len(points)-1):\n",
    "            for j in range(i+1, len(points)):\n",
    "                y_dist = points[j][1] - points[i][1]\n",
    "                x_dist = points[j][0] - points[i][0]\n",
    "                if x_dist == 0:\n",
    "                    zero_y = float('inf')\n",
    "                    tangle = float('inf')\n",
    "                else:\n",
    "                    tangle = y_dist/x_dist\n",
    "                    zero_y = points[i][0] - (points[i][0] * tangle)\n",
    "                key = (zero_y, points[i][0], tangle)\n",
    "                if key not in record:\n",
    "                    record[key] = set()\n",
    "                record[key].add(i)\n",
    "                record[key].add(j)\n",
    "        max_len = 0\n",
    "        max_indexes = []\n",
    "        for value in record.values():\n",
    "            if len(value) > max_len:\n",
    "                max_indexes = [sorted(list(value))[:2]]\n",
    "                max_len = len(value)\n",
    "            elif len(value) == max_len:\n",
    "                max_indexes.append(sorted(list(value))[:2])\n",
    "        return sorted(max_indexes, key=lambda x: (x[0], x[1]))[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        n = len(points)\n",
    "        def func(x,y):\n",
    "            if x[0]==y[0]:\n",
    "                k,b = inf,x[0]\n",
    "            else:\n",
    "                k = (y[1]-x[1])/(y[0]-x[0])\n",
    "                b = y[1]-k*y[0]\n",
    "            return (k,b)\n",
    "        acc = collections.defaultdict(set)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                tmp = func(points[i],points[j])\n",
    "                acc[tmp].add(i)\n",
    "                acc[tmp].add(j)\n",
    "        ans = list(acc.values())\n",
    "        ans.sort(key=lambda x:-len(x))\n",
    "        tmp = len(ans[0])\n",
    "        res = [inf,inf]\n",
    "        for i in range(len(ans)):\n",
    "            if len(ans[i])!=tmp:\n",
    "                break\n",
    "            re = sorted(list(ans[i]))\n",
    "            if re[0]<res[0] or (re[0]==res[0] and re[1]<res[1]):\n",
    "                res = re[:2]\n",
    "        return res\n",
    "        \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
